Ever since the advent of the first transatlantic cable back in back in 1858, which to the disappointment of its backers, was only capable of transmitting data at a rate of about 100 words every 16 hours, the impact of imperfect data channels on communications speed and reliability has been apparent to the telecommunications industry.
Making a quick transition to modern times, even modern day electronic wires (e.g. CATV cable), optical fibers, and wireless (radio) methods of data transmission suffer from the effects of imperfect data channels. The data channels are often imperfect because they often contain various signal reflectors that are positioned at various physical locations in the media (e.g. various junctions in a 1D electrical conductor such as wires, or 1D junctions in optical conductors such as optical fiber. For wireless communications, where the media is 3D space, these reflectors can be radio reflectors that are positioned at various locations in space).
Regardless of media type and reflector type, reflectors typically distort signal waveforms by creating various echo reflections, frequency shifts, and the like. The net result is that what was originally a clear and easy to interpret signal waveform, sent by a data channel transmitter will, by the time it reaches the receiver, can be degraded by the presence of various echoes and frequency shifted versions of an original signal waveform.
Traditionally, the telecommunications industry has tended to cope with to such problems by using statistical models of these various data channel reflectors and other impairments to create a statistical profile of how the state of a given data channel (channel state) may fluctuate on a statistical basis. Such prior art includes the work of Clarke and Jakes (R. H. Clarke, A statistical theory of mobile-radio reception, Bell Syst. Tech. J., 47, 957-1000 (1968); and W. C. Jakes (ed.), Microwave Mobile Communications, Wiley, New York, 1974)) and indeed such methods are often referred to in the industry as Clarke-Jakes models.
These prior art models were useful because they helped communications engineers conservatively design equipment that would generally be robust enough for various commercial applications. For example, if the statistical model predicted that waveforms too close together in frequency would tend to be smeared onto each other by channel state with some statistical probability, then the communications specifications could be designed with enough frequency separation between channels to function to some level of statistical probability. Similarly if the statistical model showed that certain statistical fluctuations in channel states would produce corresponding fluctuations in signal intensity, then the power of the transmitted waveforms, or the maximum rate of data transmission, or both could be designed to cope with these statistical fluctuations.
A good review of these various issues is provided by Pahlavan and Levesque, “Wireless Information Networks, Second Edition”, 2005, John Wiley & Sons, Inc., Hoboken N.J. This book provides a good prior art review discussing how wireless radio signals are subject to various effects including multi-path fading, signal-drop off with distance, Doppler shifts, and scattering off of various reflectors.
As a specific example of prior art, consider the challenge of designing equipment for mobile cellular phones (cell phones). When a moving cell phone receives a transmission from non-moving cell phone tower (base station), although some wireless energy from the cell phone tower may travel directly to the cell phone, much of the wireless energy from the cell phone tower transmission will typically reflect off of various reflectors (e.g. the flat side of buildings), and these “replicas” of the original cell phone tower transmission will also be received by the cell phone, subject to various time delays and power loss due to the distance between the cell phone tower, the reflector, and the cell phone.
If the cell phone is moving, the reflected “replica” of the original signal will also be Doppler shifted to a varying extent. These Doppler shifts will vary according to the relative velocity and angle between the cell phone tower, the cell phone, and the location of the various buildings (reflectors) that are reflecting the signal.
According to prior art such as the Clarke-Jakes models, statistical assumptions can be made regarding average distributions of the transmitters, receivers, and various reflectors. This statistical model can then, for example be used to help set system parameters and safety margins so that, to a certain level of reliability, the system still function in spite of these effects. Thus prior art allowed reasonably robust and commercially useful systems to be produced.
Review of OTFS Methods
Wireless communications operate by modulating signals and sending these wireless (e.g. radio) signals over their respective wireless medium or “data channel” (e.g. empty air space containing various reflectors). This wireless data channel thus consists of the physical medium of space (and any objects in this space) comprising three dimensions of space and one dimension of time. In the most commonly used commercial setting of ground based wireless applications, often the third spatial dimension of height can be less important, and thus ground based wireless applications can often be adequately approximated as a two dimensional medium of space (with objects) with one dimension of time.
As previously discussed, as wireless signals travel through their space “data channel”, the various signals (e.g. waveforms), which travel at the speed of light, are generally subject to various types of degradation or channel impairments. These echo signals can also potentially be generated when wireless signals bounce off of wireless reflecting surfaces, such as the sides of buildings, and other structures. For wireless signals, signals transmitted to or from a moving reflector, or to or from a moving vehicle are subject to Doppler shifts that also result in frequency shifts.
As previously discussed, these echo effects and frequency shifts are unwanted, and if such shifts become too large, can result in lower rates of signal transmission, as well as higher error rates. Thus methods to reduce such echo effects and frequency shifts are of high utility in the communications field.
In previous work, exemplified by applicant's US patent applications U.S. 61/349,619, U.S. Ser. Nos. 13/430,690, and 13/927,091, 14/583,911, as well as U.S. Pat. Nos. 8,547,988 and 8,879,378, applicant taught a novel method of wireless signal modulation that operated by spreading data symbols over a larger range of times, frequencies, and spectral shapes (waveforms) than was previously employed by prior art methods (e.g. greater than such prior art methods as Time Division Multiple Access (TDMA), Global System for Mobile Communications (GSM), Code Division Multiple Access (CDMA), Frequency Division Multiple Access (FDMA), Orthogonal Frequency-Division Multiplexing (OFDM), or other methods).
Applicant's methods, previously termed “Orthonormal Time-Frequency Shifting and Spectral Shaping (OTFSSS)” in U.S. Ser. No. 13/117,119 (and subsequently referred to by the simpler “OTFS” abbreviation in later patent applications such as U.S. Ser. No. 13/430,690) operated by sending data in larger “chunks” or frames than previous methods. That is, while a prior art CDMA or OFDM method might encode and send units or frames of “N” symbols over a communications link (e.g. data channel) over a set interval of time, applicant's OTFS methods might, for example, be based on a minimum unit or frame of N2 symbols, and often transmit these N2 symbols over longer periods of time.
In some OTFS modulation embodiments, each data symbol or element that is transmitted was also spread out to a much greater extent in time, frequency, and spectral shape space than was the case for prior art methods. As a result, at the receiver end, it often took longer to start to resolve the value of any given data symbol because this symbol had to be gradually built-up or accumulated as the full frame of N2 symbols (for example) is received.
Thus inventors' prior work related to a wireless communication method that used a combination of time, frequency and spectral shaping to transmit data in convolution unit matrices (data frames) of N·N (N2) (e.g. N×N, N times N) symbols. In some embodiments, either all N2 data symbols are received over N spreading time intervals (e.g. N wireless waveform bursts), or none were (e.g. receiving N bursts was required in order to reconstruct the original data bits). In other embodiments this requirement was relaxed.
To determine the times, waveforms, and data symbol distribution for the transmission process, the N2 sized data frame matrix could, for example, be multiplied by a first N·N time-frequency shifting matrix, permuted, and then multiplied by a second N·N spectral shaping matrix, thereby mixing each data symbol across the entire resulting N·N matrix. This resulting data matrix was then selected, modulated, and transmitted, on a one element per time slice basis, as a series of N OTFS symbol waveform bursts. At the receiver, the replica matrix was reconstructed and deconvoluted, revealing a copy of the originally transmitted data.
For example, in some embodiments taught by U.S. patent application Ser. No. 13/117,119, the OTFS waveforms could be transmitted and received on one frame of data ([D]) at a time basis over a communications link, typically using processor and software driven wireless transmitters and receivers. Thus, for example, all of the following steps were usually done automatically using at least one processor.
This first approach used frames of data that would typically comprise a matrix of up to N2 data elements, N being greater than 1. This method was based on creating an orthonormal matrix set comprising a first N×N matrix ([U1]) and a second N×N matrix ([U2]). The communications link and orthonormal matrix set were typically chosen to be capable of transmitting at least N elements from a matrix product of the first N×N matrix ([U1]), a frame of data ([D]), and the second N×N matrix ([U2]) over one time spreading interval (e.g. one burst). Here each time spreading interval could consist of at least N time slices. The method typically operated by forming a first matrix product of the first N×N matrix ([U1]), and the frame of data ([D]), and then permuting the first matrix product by an invertible permutation operation P, resulting in a permuted first matrix product P([U1][D]). The method then formed a second matrix product of this permuted first matrix product P([U1][D]) and the second N×N matrix ([U2]) forming a convoluted data matrix, according to the method, this convoluted data matrix could be transmitted and received over the wireless communications link.
On the transmitter side, for each single time-spreading interval (e.g. burst time), the method operated by selecting N different elements of the convoluted data matrix, and over different time slices in this time spreading interval, the method used a processor and typically software controlled radio transmitters to select one element from the N different elements of the convoluted data matrix, modulate this element, and wirelessly transmit this element so that each element occupied its own time slice.
On the receiver side, the receiver (typically a processor controlled software receiver) would receive these N different elements of the convoluted data matrix over different time slices in the various time spreading intervals (burst times), and demodulate the N different elements of this convoluted data matrix. These steps would be repeated up to a total of N times, thereby reassembling a replica of the convoluted data matrix at the receiver.
The receiver would then use the first N×N matrix ([U1]) and the second N×N matrix ([U2]) to reconstruct the original frame of data ([D]) from the convoluted data matrix. In some embodiments of this method, an arbitrary data element of an arbitrary frame of data ([D]) could not be guaranteed to be reconstructed with full accuracy until the convoluted data matrix had been completely recovered. In practice, the system could also be configured with some redundancy so that it could cope with the loss of at least a few elements from the convoluted data matrix.
U.S. patent application Ser. No. 13/117,119 and its provisional application 61/359,619 also disclosed some embodiments for an alternative approach of transmitting and receiving at least one frame of data ([D]) over a wireless communications link, where again this frame of data generally comprised a matrix of up to N2 data elements (N being greater than 1). This alternative method worked by convoluting the data elements of the frame of data ([D]) so that the value of each data element, when transmitted, would be spread over a plurality of wireless waveforms, where each individual waveform in this plurality of wireless waveforms would have a characteristic frequency, and each individual waveform in this plurality of wireless waveforms would carry the convoluted results from a plurality of these data elements from the data frame. According to the method, the transmitter automatically transmitted the convoluted results by cyclically shifting the frequency of this plurality of wireless waveforms over a plurality of time intervals so that the value of each data element would be transmitted as a plurality of cyclically frequency shifted wireless waveforms sent over a plurality of time intervals, again as a series of waveform bursts. At the receiver side, a receiver would receive and use a processor to deconvolute this plurality of cyclically frequency shifted wireless waveforms bursts sent over a plurality of times, and thus reconstruct a replica of at least one originally transmitted frame of data ([D]). Here again, in some embodiments, the convolution and deconvolution schemes could be selected so such that an arbitrary data element of an arbitrary frame of data ([D]) could not be guaranteed to be reconstructed with full accuracy until substantially all of the plurality of cyclically frequency shifted wireless waveforms had been transmitted and received as a plurality of waveform bursts. In practice, as before, system could also be configured with some redundancy so that it could cope with the loss of at least a few cyclically frequency shifted wireless waveforms.
U.S. patent application Ser. No. 13/430,690 disclosed some embodiments of OTFS methods of transferring a plurality of data symbols using a signal modulated to allow automatic compensation for the signal impairment effects of echo reflections and frequency offsets. This method comprised distributing the plurality of data symbols into one or more N×N symbol matrices, and then using these one or more N×N symbol matrices to control the signal modulation of a transmitter. Here the scheme was that for each N×N symbol matrix, the transmitter would use each data symbol to weight N waveforms, where these waveforms were selected from a N2 sized set of all permutations of N cyclically time shifted and N cyclically frequency shifted waveforms determined according to an encoding matrix U. This process thus produced N symbol-weighted cyclically time shifted and cyclically frequency shifted waveforms for each data symbol. The encoding matrix U was chosen to be an N×N unitary matrix that has a corresponding inverse decoding matrix UH. Thus for each data symbol in the N×N symbol matrix, the OTFS system and method operated by summing the N symbol-weighted cyclically time shifted and cyclically frequency shifted waveforms, producing N2 summation-symbol-weighted cyclically time shifted and cyclically frequency shifted waveforms. The OTFS transmitter then transmitted these N2 summation-symbol-weighted cyclically time shifted and cyclically frequency shifted waveforms, structured as N composite waveforms, over any combination of N time blocks or frequency blocks.
U.S. patent application Ser. No. 13/927,088 disclosed some embodiments of OTFS methods that provided a modulated signal useable in a signal transmission system. This version of the OTFS method comprised establishing an original data frame having a first dimension of at least N elements and a second dimension of at least N elements, wherein N is greater than one. This original data frame is then transformed in accordance with a time-frequency transformation so as to provide a transformed data matrix. Here the time-frequency transformation is performed using a time-frequency shifting matrix wherein the time-frequency shifting matrix is of a first dimension having N elements and of a second dimension having N elements, where N is greater than one. The OTFS transmitter then generates the modulated signal in accordance with elements of the transformed data matrix.
U.S. patent application Ser. No. 13/927,086 disclosed some embodiments of OTFS methods that provided a method of data modulation, comprising arranging a set of data elements into an original data frame having a first dimension of N elements and a second dimension of N elements, where N is greater than one, and then transforming the original data frame in accordance with a time-frequency shifting matrix so as to form an intermediate data matrix having at least N2 elements. The method also operates by providing a transformed data matrix by permuting at least a portion of the elements of the intermediate data matrix; and generating a modulated signal based upon elements of the transformed data matrix. Here this generation process includes selecting the elements of the transformed data matrix on a column by column basis at different times, wherein the transformed data matrix includes at least N columns and at least N rows.
U.S. application Ser. No. 13/927,086 also taught OTFS methods that provided a method of receiving data comprising: receiving data signals corresponding to a transmitted data frame comprised of a set of data elements, and then constructing, based upon the data signals, a received data frame having a first dimension of at least N elements and a second dimension of at least N elements, where N is greater than one. This method then operated by inverse permuting at least a portion of the elements of the received data frame so as to form a non-permuted data frame. This in turn was then inverse transformed in accordance with a first inverse-transformation matrix so as to form a recovered data frame corresponding to a reconstructed version of the transmitted data frame. This receiving method thus determined an existence of signal distortion within the received data signals, where the signal distortion was indicative of a channel distortion relating to at least one of a frequency shift and a time shift.
In other embodiments, the methods previously disclosed in U.S. patent application Ser. Nos. 13/927,091; 13/927/086; 13/927,095; 13/927,089; 13/927,092; 13/927,087; 13/927,088; 13/927,091; 14/583,911; and/or provisional applications 62/129,930, 61/664,020, and 62/027,231 may be used for some of the OTFS modulation methods disclosed herein. The entire contents of U.S. patent applications 62/027,231, 62/129,930, Ser. Nos. 13/927,091; 13/927/086; 13/927,095; 13/927,089; 13/927,092; 13/927,087; 13/927,088; 13/927,091; 14/583,911 and 61/664,020 are incorporated herein in their entirety.